/**以特定角度行进的寻路方式
 * 相关概念：
 * currentNode:当前节点
 * parentNode:父节点
 * startNode:起始节点
 * endNode:终点节点
 * childNode:子节点
 * compareList:比较选择列表。该列表保存寻路过程中生成的按总代价升序排列的子节点，当前节点被否定时，将从该列表重新获取当前节点。
 *
 * 寻路过程：
 * @
注意point和node的区别，也就是点和节点的区别
 
 */
package com.gamebase.findPath
{
	import com.gamebase.findPath.PathNode;
	
	import flash.display.MovieClip;
	import flash.geom.Point;
	
	public class AnglePath
	{
		private var _startPoint:Point = new Point();//起始点
		private var _endPoint:Point = new Point();//目标点
		private var compareList:Array = new Array();//比较节点列表(也叫开放列表)
		private var parentNode:PathNode;//每一次找完子点的时候都要将当前出发节点更新为父节点
		private var _pathAngles:Array;//可能的寻路方向，互补的角只写一个，使用角度值，默认间隔45度寻路
		private var _roadMC:MovieClip;//通道剪辑
		private var _baffleMC:MovieClip;//障碍物剪辑
		private var d:Number = 30;//通道直径，不是_roadMC的半径，在通道方式寻路时使用
		private var shortestChildNode:PathNode;//最短子节点
		
		public var stepLen:Number = 10;//步长
		public var m_PathArr:Array;//最终路径 
		
		public function AnglePath(roadMC:MovieClip=null , baffleMC:MovieClip = null , pathAngles:Array=null)
		{
			if(roadMC)
			{
				_roadMC = roadMC;
			}
			if(baffleMC)
			{
				_baffleMC = baffleMC;
			}
			
			if(pathAngles)
				_pathAngles = pathAngles;
			else
				_pathAngles =[0,45,90,135];
			
			_pathAngles.forEach(makeAngle);
			trace(_pathAngles.toString());
			
		}
		
		//生成行进角度
		private function makeAngle(item:*,index:int,arr:Array):void
		{
			arr.splice(index,1,item/180*Math.PI)
			//构建item的补角
			var compareItem:Number
			if(item<180)
				compareItem = item + 180;
			else
				compareItem = item - 180;
			
			compareItem = compareItem/180*Math.PI;
			arr.push(compareItem);
		}
		
		//获取两点间的距离
		private function getTweenLen(p1:Point,p2:Point):Number
		{
			return Math.sqrt(Math.pow((p1.x-p2.x),2)+Math.pow((p1.y-p2.y),2));
		}
		
		//查看两点之间是否有障碍物
		private function isPassPath(p1:Point,p2:Point):Boolean
		{
			var movedLen:Number = 0;
			var totalLen:Number = Point.distance(p1,p2);
			while(movedLen < totalLen)
			{
				movedLen += this.stepLen;
				if(hitTestPoint(new Point(movedLen/totalLen*(p2.x - p1.x),movedLen/totalLen*(p2.y - p1.y)),_baffleMC))
				{
					return false;
					break;
				}
			}
			return true;	
		}
		
		//检查点是否在通道或障碍物上
		private function hitTestPoint(p:Point,hitObject:MovieClip):Boolean
		{
			var localPoint:Point = hitObject.globalToLocal(p);
			if(hitObject.hitTestPoint(localPoint.x,localPoint.y))//..
			{
				return true;
			}
			else
				return false;
		}
		
		//找子点
		private function findChildPoints(beginPoint:Point):Array
		{
			var arr:Array = new Array();//各方向的拐点集合
			var j:uint=0;
			var n:uint;
			var angNum:uint = _pathAngles.length;
			var lastPoint:Point = beginPoint;
			var currentPoint:Point = beginPoint;
			var turnPoint:Point = new Point();
			var hasTurnPoint:Boolean;
			
			while(j<this._pathAngles.length)
			{
				while(true)//从_pathAngles[j]寻路方向找拐点作为子点，该子点必须是岔路点或者_startPoint
				{
					lastPoint = currentPoint;
					currentPoint = new Point();
					currentPoint.x = currentPoint.x + stepLen*Math.cos(_pathAngles[j]);
					currentPoint.y = currentPoint.y - stepLen*Math.sin(_pathAngles[j]);
					if(hitTestPoint(currentPoint,_roadMC))
					{//检查currentPoint是否是岔路点
						n=0;
						hasTurnPoint = false;
						while(n<_pathAngles.length)
						{
							if((_pathAngles[n] == _pathAngles[j]) || (_pathAngles[n]==_pathAngles[(j+angNum/2)>angNum?(j-angNum/2):(j+angNum/2)]))
								continue;
							turnPoint.x = currentPoint.x + d*Math.cos(_pathAngles[n]);
							turnPoint.y = currentPoint.y - d*Math.sin(_pathAngles[n]);
							if(hitTestPoint(turnPoint,_roadMC))
							{
								arr.push(currentPoint);
								hasTurnPoint = true;
								break;
							}
							n++;
						}
						if(hasTurnPoint)
							break;
					}
					else
					{//如果超出通道
						if(getTweenLen(currentPoint,_startPoint)<stepLen)//
							arr.push(_startPoint);
						break;
					}
				}
				j++;
			}
			return arr;
		}
		
		//从compareList中获取路程最短的节点
		private function getShortestCompareNode():PathNode
		{
			var shortIndex:uint = 0
			var shortLen:Number = compareList[shortIndex][0].totalLen;
			for(var k:uint=1; k<compareList.length; k++)
			{
				if(compareList[k][0].totalLen < shortLen)
				{
					shortLen = compareList[k][0].totalLen;
					shortIndex = k;
				}
			}
			return compareList[shortIndex].shift();
		}
		
		//将子点包装成子节点，选取路径最短的子节点,其它子节点组成一个按totalLen降序排列的数组放入比较节点列表
		private function selectChildNode(childPointList:Array):PathNode
		{
			var selectNode:PathNode;
			var childNodes:Array = new Array();
			var i:uint = 0;
			var childNode:PathNode = new PathNode();
			var len:Number
			
			while(i<childPointList.length)
			{
				childNode = new PathNode();
				len = Point.distance(childPointList[i] , _startPoint);
				//childNode.nodeName = "p"+childPointList[i].x+"_"+childPointList[i].y;
				childNode.point = childPointList[i];
				childNode.passPoints = parentNode.passPoints.concat(childNode.point);
				childNode.lessLen = len;
				childNode.passLen = parentNode.passLen + parentNode.point.subtract(childNode.point);
				childNode.totalLen = childNode.lessLen + childNode.passLen;
				childNode.negative = false;//？
				childNodes.push(childNode);
				
				i++;
			}
			//childNodes.splice(childNodes.indexOf(selectNode),1);
			childNodes.sortOn("totalLen" , Array.NUMERIC);
			selectNode = childNodes.shift();
			compareList.push(childNodes);
			return selectNode;
		}
		
		//开始搜索路径
		public function findPassPath(startPoint:Point,endPoint:Point):Array
		{
			_startPoint = startPoint;
			_endPoint = endPoint;
			compareList.length = 0;
			
			var childPoints:Array = new Array();//当前节点的子点列表
			var maxSearchNum:uint = 1000;//最多搜索次数
			var searchNum:uint = 0;//当前搜索次数
			//将目标点设置成父节点
			parentNode = new PathNode();
			parentNode.point = _endPoint;
			parentNode.lessLen = getTweenLen(parentNode.point , _startPoint);
			
			childPoints = findChildPoints(_endPoint);
			if(childPoints.length>0)
				shortestChildNode = selectChildNode(childPoints);
			else
			{
				m_PathArr = [];
				return m_PathArr;
			}
				
			if(shortestChildNode.point.equals(_startPoint))
			{
				m_PathArr = shortestChildNode.passPoints;
				return m_PathArr;
			}
				
			//
			while(searchNum < maxSearchNum)
			{
				if(shortestChildNode.point.equals(_startPoint))//找到起始点_startPoint
				{
					m_PathArr = shortestChildNode.passPoints;
					return m_PathArr;
					break;
				}
				
				parentNode = shortestChildNode;
				childPoints = findChildPoints(shortestChildNode.point);
				if(childPoints.length>0)
				{
					shortestChildNode = selectChildNode(childPoints);
					if(shortestChildNode.negative)
					{
						compareList[compareList.length -1].unshift(shortestChildNode);
						shortestChildNode = getShortestCompareNode();
						parentNode = shortestChildNode;
						continue;
					}
				}
				else
				{//从比较列表中重新获取路径最短的节点
					shortestChildNode = getShortestCompareNode();
					parentNode = shortestChildNode;
					continue;
				}
				
				searchNum++;
			}
			
			m_PathArr = shortestChildNode.passPoints
			return m_PathArr;
		}

	}
}